package 将x减到0的最小操作数.src;/*
* leetcode 1658 将x减到0的最小操作数
* 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除
* 数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。
* 请注意，需要 修改 数组以供接下来的操作使用。
* 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
*
* 示例 1：
* 输入：nums = [1,1,4,2,3], x = 5
* 输出：2
* 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
*
* 示例 2：
* 输入：nums = [5,6,7,8,9], x = 4
* 输出：-1
* */

public class Project01 {
    public int minOperations(int[] nums, int x) {
        int n=nums.length,target=0,sum=0,max=-1;
        for(int i=0;i<n;i++){
            target+=nums[i];
        }
        target-=x; //将找两边问题转化为找中间
        if(target<0)return -1; //小优化
        for(int l=0,r=0;r<n;r++){
            sum+=nums[r]; //进窗口
            while(sum>target&&l<=r){ //判断
                sum-=nums[l++]; //出窗口
            }
            if(sum==target){
                max=Math.max(max,r-l+1); //更新结果
            }
        }
        return max==-1?-1:n-max;
    }
}
